package com.lw.leetcode.dp.c;

/**
 * Created with IntelliJ IDEA.
 * 801. 使序列递增的最小交换次数
 *
 * @author liw
 * @version 1.0
 * @date 2022/7/29 17:10
 */
public class MinSwap {

    public static void main(String[] args) {
        MinSwap test = new MinSwap();

        // 1
//        int[] arr1 = {1, 3, 5, 4};
//        int[] arr2 = {1, 2, 3, 7};

        // 0
//        int[] arr1 = {1, 3, 5};
//        int[] arr2 = {1, 2, 3};

        // 1
        int[] arr1 = {0, 3, 5, 8, 9};
        int[] arr2 = {2, 1, 4, 6, 9};

        int i = test.minSwap(arr1, arr2);
        System.out.println(i);


    }

    public int minSwap(int[] nums1, int[] nums2) {
        int length = nums1.length;
        int[][] arr = new int[length][2];
        arr[0][1] = 1;
        for (int i = 1; i < length; i++) {
            int a = nums1[i];
            int b = nums2[i];
            int a1 = nums1[i - 1];
            int b1 = nums2[i - 1];
            if (a > a1 && b > b1) {
                if (a > b1 && b > a1) {
                    arr[i][0] = Math.min(arr[i - 1][0], arr[i - 1][1]);
                    arr[i][1] = Math.min(arr[i - 1][0], arr[i - 1][1]) + 1;
                } else {
                    arr[i][0] = arr[i - 1][0];
                    arr[i][1] = arr[i - 1][1] + 1;
                }
            } else {
                arr[i][0] = arr[i - 1][1];
                arr[i][1] = arr[i - 1][0] + 1;
            }
        }
        return Math.min(arr[length - 1][0], arr[length - 1][1]);
    }

}
